МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
/
Лабораторна робота №5
з дисципліни “Математичні методи дослідження операцій”
на тему
«Двоїста задача лін. програмування. Економічна інтерпретація.
Двоїстий симплекс-метод.»
Львів –
Мета роботи: вивчення двоїстої задачі лінійного програмування із застосування симплекс методу для знаходження розв’язку.
План
Короткі теоретичні відомості.
Постановка задачі
Двоїста задача задача із застосуванням сиплекс методу.
Розв’язання за допомогою пакету програм SimplexWin
Розв’язання за допомогою власної програми.
Хід роботи
1. Короткі теоретичні відомості
Кожній задачі лінійного програмування
відповідає двоїста
Спільний розгляд таких пар задач дозволяє проводити економічний аналіз результатів розрахунку.
Пряма задача (мах) – розподіл обмежених ресурсів між різними споживачами, напр. між деякими технологічними процесами – стовпці матриці А.
Рішення задачі (х1,х2,…,хn) вказує ту долю кожного із ресурсів хj, щоб отримати максимум прибутку.
Завод випускає три види продукції х1,х2,х3 . кожен вид продукції вимагає затрат часу на обробку на токарному, фрезельному і свердлильному станках. Кількість машинного часу для кожного із станків обмежена. Нехай с1,с2,с3 – прибуток від одиниці відповідного виду продукції. Необхідно визначити, яку кількість кожного виду продукції (хj) необхудно випускати протягом визначеного часу, щоб отримати максимальний прибуток
Обмеження
де а1j, а2j, а3j - час необхідний для обробки одиниці j-го виду продукції відповідно на токарному, фрезерному і свердлильному станках (j = 1,2,3);
b1, b2, b3 - ресурс машинного часу відповідно для токарного, фрезерного і свердлильного станків.
Для переходу до двоїстої задачі
Позначимо
y1, y2, y3 – ціну одиниці часу роботи на токарному, фрезерному і свердлильному станках: (yi>0).
Тоді
витрати на виробництво Fmin при умові, що сумарні затрати на одиницю продукції не менше вартості товару.
Обмеження
Основна теорема двоїстості
Для оптимальних рішень пар двоїстих задач виконується умова :
Двоїсту задачу вигідно розв’язувати, коли в прямій задачі при малій кількості змінних є велика кількість обмежень (m > n).
2. Постановка задачі
Розв’язати двоїсту задачу лінійного програмування (номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером 100)
Варіант 21
F(x1,x2) = 3x1 + 2x2 min ;
4x1 + 2x2 12,
x1 + 2x2 10,
2x1 + 2x2 = 6,
x1 0, x2 0.
2.1 Розв’язання без використання пакетів програм.
Двоїста задача задача із застосуванням сиплекс методу.
Відповідно після перетворення :
4x1 + 2x2 12,
x1 + 2x2 10,
2x1 + 2x2 = 6,
F(x1,x2) = 4y1 + 4y2 – 4y3
aij
5y1-1y2-1y3 -3
-2y1+2y2-1y3 6
Тобто:
кофіцієнти цільової функції прямої задачі с1,с2,…,сn стають вільними членами обмежень двоїстої задачі.
Вільні члени обмежень прямої задачі b1,b2,…,bn стають коефіцієнтами цільової функції двоїстої задачі.
Матрицю обмежень двоїстої задачі отримують транспонуванням матриці обмежень прямої задачі.
Число змінних двоїстої задачі рівне числу обмежень прямої, а число обмежень двоїстої рівне числу змінних прямої, і навпаки.
Взаємно однозначна відповідність між змінними прямої задачі і обмеженнями двоїстої:
j-е обмеження двоїстої задачі буде нерівністю, якщо на j-у змінну прямої задачі накладена вимога невід’ємності, а в іншому випадку – j-е обмеження буде рівністю.
Крок 1
Обчислення оптимальності плану симплекс методом з використанням симплекс таблиць.
Спочатку додам у таблицю 2 додаткові змінні z1 i z2 , а також 1 штучний базис.
Крок 1
Базис
B
y 1
y 2
y 3
y 4
y 5
z 1
z1
3
5
-1
-1
-1
0
1
y5
6
2
-2
1
0
1
0
F(X)
-3M
-5M+4
M+4
M-4
M
0
0
Крок 2
Вибираю ключовий елемент по максимальному значенні по модулі.
Крок 2
Базис
B
y 1
y 2
y 3
y 4
y ...
